package com.cat.binaryTree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/description/
 * @create 2025/9/29 11:48
 * @since JDK17
 */

public class Solution87 {
    public long kthLargestLevelSum(TreeNode root, int k) {
        long sum = 0;
        PriorityQueue<Long> heap = new PriorityQueue<>((a, b) -> Long.compare(b, a));
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            sum = 0;
            for (int i = 0, end = q.size(); i < end; i++) {
                var p = q.poll();
                sum += p.val;
                if (p.left != null) {
                    q.add(p.left);
                }
                if (p.right != null) {
                    q.add(p.right);
                }
            }
            heap.add(sum);
        }
        if (heap.size() < k) {
            return -1;
        }
        long ans = -1;
        for (int i = 0; i < k; i++) {
            ans = heap.poll();
        }
        return ans;
    }
}
